package mo.tags.stack;

import mo.common.ListNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class L143 {

    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> nodes = new ArrayList<>();
        ListNode t = head;
        while (t != null) {
            nodes.add(t);
            t = t.next;
        }
        Queue<ListNode> queue = new LinkedList<>();
        int start = 0, end = nodes.size() - 1;
        while (start < end) {
            queue.add(nodes.get(start));
            queue.add(nodes.get(end));
            start++;
            end--;
            if (start == end) {
                queue.add(nodes.get(start));
            }
        }
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            queue.poll().next = queue.peek();
        }
    }

}
